#define  _CRT_SECURE_NO_WARNINGS 1
#include"heap.h"

void HpInit(heap* php)
{
	assert(php);
	php->arr = NULL;
	php->capacity = php->size = 0;
}

void HpDestroy(heap* php)
{
	assert(php);
	if (php->arr)
		free(php->arr);
	php->arr = NULL;
	php->size = php->capacity = 0;
}

void Swap(int* x, int* y)
{
	int tmp = 0;
	tmp = *x;
	*x = *y;
	*y = tmp;
}

void Adjustup(HPDatatype* arr, int child)
{
	int parent = (child - 1) / 2;
	while(child > 0)
	{
		//大堆  <
		//小堆  >
		if (arr[parent] < arr[child])
		{
			/*HPDatatype tmp;
			tmp = arr[parent];
			arr[parent] = arr[child];
			arr[child] = tmp;*/
			Swap(&arr[parent], &arr[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else {
			break;
		}
	}

}

void HpPush(heap* php, HPDatatype x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDatatype* tmp = (HPDatatype*)realloc(php->arr , newcapacity * sizeof(HPDatatype));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		php->arr = tmp;
		php->capacity = newcapacity;
	}
	php->arr[php->size] = x;
	Adjustup(php->arr, php->size);
	++php->size;

}

void HpPrint(heap* php)
{
	for (int i = 0; i < php->size; i++)
	{
		printf("%d ", php->arr[i]);
	}

	printf("\n");

}

bool HpEmpty(heap* php) 
{
	assert(php);
	return php->size == 0;

}

void Adjustdown(HPDatatype* arr,int n,int parent)
{
	int child = 2 * parent + 1;

	while (child < n)
	{
		//小堆 >
		//大堆 <
		if ((child+1 < n) && (arr[child] < arr[child+1]))
		{
			child++;
		}
		//小堆 >
		//大堆 <
		if (arr[parent] < arr[child])
		{
			Swap(&arr[parent], &arr[child]);
			parent = child;
			child = 2 * parent + 1;
		}
		else {
			break;
		}

	}

}

void HpPop(heap* php)
{
	assert(!HpEmpty(php));
	Swap(&php->arr[php->size - 1], &php->arr[0]);
	php->size--;
	//向下调整法
	Adjustdown(php->arr,php->size,0);

}


HPDatatype HpTop(heap* hp)
{
	assert(!HpEmpty(hp));
	return hp->arr[0];

}

//小堆（取堆顶）  升序
//大堆（取堆顶）  降序